Systems where Only a Sub-Set May be Verified
Most computer programs have options that allow the user to adapt the program according to, for example, user preferences or available computer hardware. Before shipping it, the developer of the computer program must not only verify all options, but also verify all combinations of all options in order to secure that the program works for all user settings. This task grows quickly with the number of options and, in the end, becomes so large that it is impossible to verify all combinations as testing time has practical limits. For this reason the developer is forced to verify a sub-set of all combinations. The question then arises what sub-set of combinations should be verified in order to achieve good verification coverage.
The same problem exists with configurable hardware, which is hardware that may be configured by the user. For example, an integrated circuit developer may purchase a configurable microprocessor which may have many configuration options such as the sizes of the caches, the number of interrupts and the memory bus width. Before shipping, the developer of the configurable microprocessor must verify all options and all combinations of options, which is also a task that quickly becomes too large as testing time has practical limits.
The same problem also exists in compatibility testing of computer systems where various programs, computers, routers etc are tested together in order to verify compatibility. The number of combinations quickly grows with the number of programs, computers and routers etc. In the end this task also becomes too large as testing time as practical limits.
To summarize, the problem exist in any system that contains many options, units, states or signals that need to be tested in combination with each other and where the total number of combinations is too large, forcing the developer to verify a sub-set. The question is what sub-set of combinations should be verified in order to achieve good verification coverage.
Pair-Wise Testing
Pair-wise testing is an existing method of selecting such a sub-set of combinations when the total number of combinations is too large to test. With pair-wise testing you limit the testing to all combinations of each option pair. E.g. if you have 4 Boolean options you don't verify exhaustively all 16 combinations, instead with pair-wise testing you only verify each pair of options. To fully verify a pair of Boolean options requires the following 4 combinations:
option1=false and option2=false
option1=false and option2=true
option1=true and option2=false
option1=true and option2=true
As you may verify several pairs in parallel (e.g. option1 and option2 may be fully tested in parallel with option3 and option4) the end result is a shorter list of option combinations to verify. In this example with 4 Boolean options it would require only 6 combinations of options for full pair-wise testing, compared with 16 combinations for exhaustive testing. As the number of options grows the benefit of doing pair-wise testing becomes even larger.
Various studies have shown that pair-wise testing may catch the majority of bugs despite only focusing on a small subset of combinations, This makes pair-wise testing a cost-effective way of finding bugs.
N-Wise Testing
N-wise testing is taking the idea of pair-wise testing a step closer to exhaustive testing (exhaustive testing is to verify all combinations). Whereas, pair-wise testing (or 2-way testing) only verifies all pairs of option settings, 3-way testing (which is N-wise testing where N is 3) verifies all triplets of option settings. As the N in N-ways testing grows the number of combinations grows rapidly. Already achieving full coverage of 3-way testing is in many cases too big a task as the testing time for that many combinations is not available. A more focused approach is necessary for higher orders of N-way testing (3-ways and above).
A Method and Apparatus for Measure and Display of Verification Coverage and Test Result
Hence, what is needed is a method for producing a test suite with good verification coverage for higher order of N-way testing in a focused way that prevents the number of combinations to increase dramatically. In order to do that, a method and apparatus is needed that may measure and display verification coverage for higher orders of N-way testing in a way that allows the user to focus on a desired sub-set of combinations. Also, the same method and apparatus is needed to display the test result for higher orders of N-way testing.
A Method and Apparatus for Root-Causing Test Failures to Find Faulty Configurations
When a bug is found then typically many different combinations of options will cause tests to fail, even though the bug may only be linked to one specific combination of options (a “combination of options” is also referred to as a “configuration”). In cases with many options it is hard to detect commonalities between failing tests and also hard to distinguish between the cause and consequences. The verification engineer has to spend a lot of time root-causing the test failures before being able to conclude which configurations are faulty. Hence, what is needed is a method and apparatus that analyses all test failures and points out the root causes, i.e. the faulty configurations.